// Package day_04_tree tree_public_parents
// @Title day_04_tree
// @Description  返回二叉树两个节点的最低公共祖先
// @Author  == 琳琳也叫王木木 ==  2021/8/31 14:07
// @Create  2021/8/31 14:07
package day_04_tree

/**
两个节点一定属于这棵树
方法1.遍历的时候，生成父节点的链

*/

// LowestCommonAncestor 返回二叉树的最近公共祖先  这个是左神的写法
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || p == root || q == root {
		return root
	}
	left := LowestCommonAncestor(root.Left, p, q)
	right := LowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	} else {
		return right
	}
}
